package uestc.lj.basic.listnode;

/**
 * 将一个链表分解成小于等于和大于的形式
 *
 * @Author:Crazlee
 * @Date:2021/11/22
 */
public class Code04_SmallerEqualBigger {
	public static class Node {
		public int value;
		public Node next;

		public Node(int data) {
			this.value = data;
		}
	}

	public static Node listPartition(Node head, int pivot) {
		//小于的头节点
		Node sH = null;
		//小于的尾节点
		Node sT = null;
		//等于的头节点
		Node eH = null;
		//等于的尾节点
		Node eT = null;
		//大于的头节点
		Node bH = null;
		//大于的尾节点
		Node bT = null;
		Node next = null;
		while (head != null) {
			next = head.next;
			head.next = null;
			if (head.value < pivot) {
				if (sH == null) {
					sH = head;
					sT = head;
				} else {
					sT.next = head;
					sT = head;
				}
			} else if (head.value == pivot) {
				if (eH == null) {
					eH = head;
					eT = head;
				} else {
					eT.next = head;
					eT = head;
				}
			} else {
				if (bH == null) {
					bH = head;
					bT = head;
				} else {
					bT.next = head;
					bT = head;
				}
			}
			head = next;
		}
		//如果有小于区域
		if (sT != null) {
			sT.next = eH;
			eT = eT == null ? sT : eT;
		}
		if (eT != null) {
			eT.next = bH;
		}
		return sH != null ? sH : (eH != null ? eH : bH);
	}
}
